最小栈

发表于 | 分类于 |
字数统计: 333 字 | 阅读时长 ≈ 1 分钟

题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:
输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。

辅助栈

  1. 建两个栈，一个正常的栈，一个最小栈存放当前栈最小值
  2. push元素时，由于栈顶保存的永远是最小值，所以当入栈时只需要比较入栈值与最小栈栈顶值即可得出最小值,将最小值存入最小栈中。
  3. 保持两个栈同步操作，出栈时也同步出栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var MinStack = function() {
   this.stack = []
   this.min_stack = []
};

MinStack.prototype.push = function(val) {
  this.stack.push(val)
  this.min_stack.push(Math.min(val, this.getMin() ?? Infinity))
};

MinStack.prototype.pop = function() {
  this.stack.pop()
  this.min_stack.pop()
};

MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1]
};

MinStack.prototype.getMin = function() {
  return this.min_stack[this.min_stack.length - 1]
};

复杂度分析

  • push、pop、top、getMin时间复杂度均为O(1)

  • 空间复杂度O(n)